import java.util.*;

public class Test {

    // 题目1：最长同值路径
    public  static  int max;
    public static int longestUnivaluePath(TreeNode root) {
        sameNode(root);
        return max == 0 ? 0 : max - 1;
    }

    public static int sameNode(TreeNode root){
        if(root == null){
            return 0;
        }

        int left = sameNode(root.left);
        int right = sameNode(root.right);
        int val = root.val;
        int left1 = 0;
        int right1 = 0;

        if(root.left != null && root.left.val == val){
            left1 = left;
        }
        if(root.right != null && root.right.val == val){
            right1 = right;
        }
        max = Math.max(max, left1 + right1 + 1);
        return Math.max(left1, right1) + 1;
    }

    public static void main1(String[] args) {
        TreeNode node1 = new TreeNode(5);
        TreeNode node2= new TreeNode(4);
        TreeNode node3 = new TreeNode(5);
        TreeNode node4 = new TreeNode(1);
        TreeNode node5 = new TreeNode(1);
        TreeNode node6 = new TreeNode(5);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.right = node6;
        int ret = longestUnivaluePath(node1);
        System.out.println(ret);
    }

    // 题目2： 二叉树的坡度
    int ret ;
    public int findTilt(TreeNode root) {
        tilt(root);
        return ret;
    }
    public int tilt(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = tilt(root.left);
        int right = tilt(root.right);
        ret += Math.abs(left - right);
        return left + right + root.val;
    }

    // 题目3：验证二叉搜索树
    // 中序遍历！ 左根右
    TreeNode pre ;
    int flag = 1;
    public boolean isValidBST(TreeNode root) {
        bst(root);
        return flag == 1;
    }

    public void bst(TreeNode root){
        if(root == null){
            return ;
        }
        bst(root.left);
        if(pre != null && root.val <= pre.val){
            flag = -1;
            return;
        }
        pre = root;
        bst(root.right);
    }

    // 题目4：叶子相似的树
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new LinkedList<>();
        List<Integer> list2 = new LinkedList<>();
        leaf(root1, list1);
        leaf(root2, list2);
        return list1.equals(list2);
    }

    public void leaf(TreeNode root, List<Integer> list){
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null){
            list.add(root.val);
        }
        leaf(root.left, list);
        leaf(root.right, list);
    }



}
